SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Rejection sampling</title>

</head>

Rejection sampling

</h1>

</header>

In <a href="Numerical_analysis" title="Numerical analysis">numerical analysis</a> and <a href="Computational_statistics" title="Computational statistics">computational statistics</a>, rejection sampling is a basic technique used to generate observations from a <a href="Probability_distribution" title="Probability distribution">distribution</a>. It is also commonly called the acceptance-rejection method or "accept-reject algorithm" and is a type of exact simulation method. The method works for any distribution in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{m}}</annotation>

</semantics>

</math><img src="./6a87a024931038d1858dc22e8a194e5978c3412e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.353ex; height:2.343ex;" alt="{\displaystyle \mathbb {R} ^{m}}" loading="lazy"> with a <a href="Probability_density_function" title="Probability density function">density</a>.

Rejection sampling is based on the observation that to sample a <a href="Random_variable" title="Random variable">random variable</a> in one dimension, one can perform a uniformly random sampling of the two-dimensional Cartesian graph, and keep the samples in the region under the graph of its density function.<a href="#cite_note-1">[1]</a><a href="#cite_note-radford03-2">[2]</a><a href="#cite_note-bishop06-3">[3]</a> Note that this property can be extended to N-dimension functions.

<div class="mw-heading mw-heading2"><h2 id="Description">Description</h2></div>

To visualize the motivation behind rejection sampling, imagine graphing the <a href="Probability_density_function" title="Probability density function">probability density function</a> (PDF) of a random variable onto a large rectangular board and throwing darts at it. Assume that the darts are uniformly distributed around the board. Now remove all of the darts that are outside the area under the curve. The remaining darts will be distributed uniformly within the area under the curve, and the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">‑positions of these darts will be distributed according to the random variable's density. This is because there is the most room for the darts to land where the curve is highest and thus the probability density is greatest.

The visualization just described is equivalent to a particular form of rejection sampling where the "proposal distribution" is uniform. Hence its graph is a rectangle. The general form of rejection sampling assumes that the board is not necessarily rectangular but is shaped according to the density of some proposal distribution (not necessarily normalized to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">) that we know how to sample from (for example, using <a href="Inversion_sampling" class="mw-redirect" title="Inversion sampling">inversion sampling</a>). Its shape must be at least as high at every point as the distribution we want to sample from, so that the former completely encloses the latter. Otherwise, there would be parts of the curved area we want to sample from that could never be reached.

Rejection sampling works as follows:

<ol><li>Sample a point on the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">‑axis from the proposal distribution.</li>

<li>Draw a vertical line at this <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">‑position, up to the y-value of the probability density function of the proposal distribution.</li>

<li>Sample uniformly along this line. If the sampled value is greater than the value of the desired distribution at this vertical line, reject the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">‑value and return to step 1; else the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">‑value is a sample from the desired distribution.</li></ol>

This algorithm can be used to sample from the area under any curve, regardless of whether the function integrates to 1. In fact, scaling a function by a constant has no effect on the sampled <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">‑positions. Thus, the algorithm can be used to sample from a distribution whose <a href="Normalizing_constant" title="Normalizing constant">normalizing constant</a> is unknown, which is common in <a href="Computational_statistics" title="Computational statistics">computational statistics</a>.

<div class="mw-heading mw-heading2"><h2 id="Theory">Theory</h2></div>

The rejection sampling method generates sampling values from a target distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> with an arbitrary <a href="Probability_density_function" title="Probability density function">probability density function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> by using a proposal distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> with probability density <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy">. The idea is that one can generate a sample value from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> by instead sampling from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> and accepting the sample from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)/(Mg(x))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)/(Mg(x))}</annotation>

</semantics>

</math><img src="./5699dad43ce8476e14d54922cdd7e244e13d6c87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.087ex; height:2.843ex;" alt="{\displaystyle f(x)/(Mg(x))}" loading="lazy">, repeating the draws from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> until a value is accepted. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> here is a constant, finite bound on the likelihood ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)/g(x)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)/g(x)}</annotation>

</semantics>

</math><img src="./2b315e81de2a653c2f6c2a03f980c0e5c3ae267b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.835ex; height:2.843ex;" alt="{\displaystyle f(x)/g(x)}" loading="lazy">, satisfying <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M<\infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M<\infty }</annotation>

</semantics>

</math><img src="./fa1b4601cdd25070b6e6c2dba6e3c330210f37c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.864ex; height:2.176ex;" alt="{\displaystyle M<\infty }" loading="lazy"> over the <a href="Support_(mathematics)" title="Support (mathematics)">support</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">; in other words, M must satisfy <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)\leq Mg(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)\leq Mg(x)}</annotation>

</semantics>

</math><img src="./51136901bea8bc9f89b161256929ee9eaa986091.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.213ex; height:2.843ex;" alt="{\displaystyle f(x)\leq Mg(x)}" loading="lazy"> for all values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. Note that this requires that the support of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> must include the support of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">—in other words, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)>0}</annotation>

</semantics>

</math><img src="./3e999e3ac462023ab594ec9281686f4525e63143.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.516ex; height:2.843ex;" alt="{\displaystyle g(x)>0}" loading="lazy"> whenever <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)>0}</annotation>

</semantics>

</math><img src="./af29e26aaac6c969d32c8afac1f33ae703f442c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.678ex; height:2.843ex;" alt="{\displaystyle f(x)>0}" loading="lazy">.

The validation of this method is the envelope principle: when simulating the pair <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle (x,v=u\cdot Mg(x))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle (x,v=u\cdot Mg(x))}</annotation>

</semantics>

</math><img src="./d7514e22ed74484bc349535d9392467e8398254e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.105ex; height:2.843ex;" alt="{\textstyle (x,v=u\cdot Mg(x))}" loading="lazy">, one produces a uniform simulation over the subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle Mg(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle Mg(x)}</annotation>

</semantics>

</math><img src="./28b0d35a0a37664c454c3c9d4ee4ac5c4df8a68a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.697ex; height:2.843ex;" alt="{\textstyle Mg(x)}" loading="lazy">. Accepting only pairs such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle u<f(x)/(Mg(x))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle u<f(x)/(Mg(x))}</annotation>

</semantics>

</math><img src="./299e1c5b9745ef1aa63b34bd890494a6678eab4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.515ex; height:2.843ex;" alt="{\textstyle u<f(x)/(Mg(x))}" loading="lazy"> then produces pairs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,v)}</annotation>

</semantics>

</math><img src="./5d8a814ed966e3a5810769d418bf795a29e2a56a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.301ex; height:2.843ex;" alt="{\displaystyle (x,v)}" loading="lazy"> uniformly distributed over the subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> and thus, marginally, a simulation from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x).}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x).}</annotation>

</semantics>

</math><img src="./e889a7f3ee0216318cbf9f3478208fa1404cc51c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.064ex; height:2.843ex;" alt="{\displaystyle f(x).}" loading="lazy">

This means that, with enough replicates, the algorithm generates a sample from the desired distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy">. There are a number of extensions to this algorithm, such as the <a href="Metropolis_algorithm" class="mw-redirect" title="Metropolis algorithm">Metropolis algorithm</a>.

This method relates to the general field of <a href="Monte_Carlo_method" title="Monte Carlo method">Monte Carlo</a> techniques, including <a href="Markov_chain_Monte_Carlo" title="Markov chain Monte Carlo">Markov chain Monte Carlo</a> algorithms that also use a proxy distribution to achieve simulation from the target distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy">. It forms the basis for algorithms such as the <a href="Metropolis_algorithm" class="mw-redirect" title="Metropolis algorithm">Metropolis algorithm</a>.

The unconditional acceptance probability is the proportion of proposed samples which are accepted, which is <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)&=\operatorname {E} \mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}\\[6pt]&=\operatorname {E} \left[\operatorname {E} [\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}|Y]\right]&({\text{by tower property }})\\[6pt]&=\operatorname {E} \left[\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}{\biggr |}Y\right)\right]\\[6pt]&=\operatorname {E} \left[{\frac {f(Y)}{Mg(Y)}}\right]&({\text{because }}\Pr(U\leq u)=u,{\text{when }}U{\text{ is uniform on }}(0,1))\\[6pt]&=\int \limits _{y:g(y)>0}{\frac {f(y)}{Mg(y)}}g(y)\,dy\\[6pt]&={\frac {1}{M}}\int \limits _{y:g(y)>0}f(y)\,dy\\[6pt]&={\frac {1}{M}}&({\text{since support of }}Y{\text{ includes support of }}X)\end{aligned}}}">

<mtr>

<mtd>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mrow>

<msub>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mtd>

<mtd>

<mtext>by tower property </mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mrow>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mtd>

<mtd>

<mtext>because </mtext>

</mrow>

</mrow>

<mtext> is uniform on </mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mrow>

</mtd>

<mtd>

<mtext>since support of </mtext>

</mrow>

<mtext> includes support of </mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)&=\operatorname {E} \mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}\\[6pt]&=\operatorname {E} \left[\operatorname {E} [\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}|Y]\right]&({\text{by tower property }})\\[6pt]&=\operatorname {E} \left[\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}{\biggr |}Y\right)\right]\\[6pt]&=\operatorname {E} \left[{\frac {f(Y)}{Mg(Y)}}\right]&({\text{because }}\Pr(U\leq u)=u,{\text{when }}U{\text{ is uniform on }}(0,1))\\[6pt]&=\int \limits _{y:g(y)>0}{\frac {f(y)}{Mg(y)}}g(y)\,dy\\[6pt]&={\frac {1}{M}}\int \limits _{y:g(y)>0}f(y)\,dy\\[6pt]&={\frac {1}{M}}&({\text{since support of }}Y{\text{ includes support of }}X)\end{aligned}}}</annotation>

</semantics>

</math>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\sim \mathrm {Unif} (0,1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U\sim \mathrm {Unif} (0,1)}</annotation>

</semantics>

</math><img src="./3c86fdfc26e7e426f8de4b9f74353f631a59ce7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.597ex; height:2.843ex;" alt="{\displaystyle U\sim \mathrm {Unif} (0,1)}" loading="lazy">, and the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> each time is generated under the density function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\cdot )}</annotation>

</semantics>

</math><img src="./421d5ab89ea154ac75586bdfb687db2160d1ea33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.572ex; height:2.843ex;" alt="{\displaystyle g(\cdot )}" loading="lazy"> of the proposal distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy">.

The number of samples required from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> to obtain an accepted value thus follows a <a href="Geometric_distribution" title="Geometric distribution">geometric distribution</a> with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/M}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/M}</annotation>

</semantics>

</math><img src="./20165e6609a305fcccbfdf5e5cac123efb8c5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.767ex; height:2.843ex;" alt="{\displaystyle 1/M}" loading="lazy">, which has mean <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">. Intuitively, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is the expected number of the iterations that are needed, as a measure of the computational complexity of the algorithm.

Rewrite the above equation, <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M={\frac {1}{\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}}}">

<mfrac>

<mrow>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M={\frac {1}{\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}}}</annotation>

</semantics>

</math>

Note that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle 1\leq M<\infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle 1\leq M<\infty }</annotation>

</semantics>

</math><img src="./b1de80040fbae5a14e2e46b26a4a934e31a7f3d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.125ex; height:2.343ex;" alt="{\textstyle 1\leq M<\infty }" loading="lazy">, due to the above formula, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}">

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}</annotation>

</semantics>

</math><img src="./426ecaafd7ff5bd3674781f588d1c205fd02cba3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:15.349ex; height:4.843ex;" alt="{\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}" loading="lazy"> is a probability which can only take values in the interval <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [0,1]}</annotation>

</semantics>

</math><img src="./738f7d23bb2d9642bab520020873cccbef49768d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle [0,1]}" loading="lazy">. When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is chosen closer to one, the unconditional acceptance probability is higher the less that ratio varies, since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is the upper bound for the likelihood ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle f(x)/g(x)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle f(x)/g(x)}</annotation>

</semantics>

</math><img src="./6f017816a536b072dd6b5ae9e80e5a154cffb8b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.835ex; height:2.843ex;" alt="{\textstyle f(x)/g(x)}" loading="lazy">. In practice, a value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> closer to 1 is preferred as it implies fewer rejected samples, on average, and thus fewer iterations of the algorithm. In this sense, one prefers to have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> as small as possible (while still satisfying <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)\leq Mg(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)\leq Mg(x)}</annotation>

</semantics>

</math><img src="./51136901bea8bc9f89b161256929ee9eaa986091.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.213ex; height:2.843ex;" alt="{\displaystyle f(x)\leq Mg(x)}" loading="lazy">, which suggests that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> should generally resemble <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> in some way. Note, however, that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> cannot be equal to 1: such would imply that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=g(x)}</annotation>

</semantics>

</math><img src="./01d0bb8fc04dfc0d04d53ee9ada38c794e51ca78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.771ex; height:2.843ex;" alt="{\displaystyle f(x)=g(x)}" loading="lazy">, i.e. that the target and proposal distributions are actually the same distribution.

Rejection sampling is most often used in cases where the form of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> makes sampling difficult. A single iteration of the rejection algorithm requires sampling from the proposal distribution, drawing from a uniform distribution, and evaluating the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)/(Mg(x))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)/(Mg(x))}</annotation>

</semantics>

</math><img src="./5699dad43ce8476e14d54922cdd7e244e13d6c87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.087ex; height:2.843ex;" alt="{\displaystyle f(x)/(Mg(x))}" loading="lazy"> expression. Rejection sampling is thus more efficient than some other method whenever M times the cost of these operations—which is the expected cost of obtaining a sample with rejection sampling—is lower than the cost of obtaining a sample using the other method.

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

The algorithm, which was used by <a href="John_von_Neumann" title="John von Neumann">John von Neumann</a><a href="#cite_note-4">[4]</a> and dates back to <a href="Georges-Louis_Leclerc%2C_Comte_de_Buffon" title="Georges-Louis Leclerc, Comte de Buffon">Buffon</a> and <a href="Buffon's_needle" class="mw-redirect" title="Buffon's needle">his needle</a>,<a href="#cite_note-5">[5]</a> obtains a sample from distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> with density <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> using samples from distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> with density <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> as follows:

<ul><li>Obtain a sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> from distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> and a sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Unif} (0,1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Unif} (0,1)}</annotation>

</semantics>

</math><img src="./0ddb5e953fba58901576ec11069da77526698b8c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.716ex; height:2.843ex;" alt="{\displaystyle \mathrm {Unif} (0,1)}" loading="lazy"> (the uniform distribution over the <a href="Unit_interval" title="Unit interval">unit interval</a>).</li>

<li>Check if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle u<f(y)/Mg(y)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle u<f(y)/Mg(y)}</annotation>

</semantics>

</math><img src="./8d5d2de23e1ba5a8a258938f125b28c5c8cff38d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.357ex; height:2.843ex;" alt="{\textstyle u<f(y)/Mg(y)}" loading="lazy">.

<ul><li>If this holds, accept <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> as a sample drawn from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">;</li>

<li>if not, reject the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> and return to the sampling step.</li></ul></li></ul>

The algorithm will take an average of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> iterations to obtain a sample.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Advantages_over_sampling_using_naive_methods">Advantages over sampling using naive methods</h2></div>

Rejection sampling can be far more efficient compared with the naive methods in some situations. For example, given a problem as sampling <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X\sim F(\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X\sim F(\cdot )}</annotation>

</semantics>

</math><img src="./4b067efa41858afa5ed040943870d0ef5483a306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.275ex; height:2.843ex;" alt="{\textstyle X\sim F(\cdot )}" loading="lazy"> conditionally on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> given the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X|X\in A}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X|X\in A}</annotation>

</semantics>

</math><img src="./7708e6af76d37a4f220f37c6af353a08fb1c2945.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.191ex; height:2.843ex;" alt="{\textstyle X|X\in A}" loading="lazy">, sometimes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X}</annotation>

</semantics>

</math><img src="./8d80c41192705e1a6c6de1d65e16d7f70fbac391.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\textstyle X}" loading="lazy"> can be easily simulated, using the naive methods (e.g. by <a href="Inverse_transform_sampling" title="Inverse transform sampling">inverse transform sampling</a>):

<ul><li>Sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X\sim F(\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X\sim F(\cdot )}</annotation>

</semantics>

</math><img src="./4b067efa41858afa5ed040943870d0ef5483a306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.275ex; height:2.843ex;" alt="{\textstyle X\sim F(\cdot )}" loading="lazy"> independently, and accept those satisfying <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{n\geq 1:X_{n}\in A\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{n\geq 1:X_{n}\in A\}}</annotation>

</semantics>

</math><img src="./f6f0f98784db3e36adc970c4943cffd7e28d2e1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.644ex; height:2.843ex;" alt="{\displaystyle \{n\geq 1:X_{n}\in A\}}" loading="lazy"></li>

<li>Output: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}}</annotation>

</semantics>

</math><img src="./71cd8bc8658cf28660b0fa0a2cf413fc07c30b13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.677ex; height:2.843ex;" alt="{\displaystyle \{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}}" loading="lazy"> (see also <a href="Truncation_(statistics)" title="Truncation (statistics)">truncation (statistics)</a>)</li></ul>

The problem is this sampling can be difficult and inefficient, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mathbb {P} (X\in A)\approx 0}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mathbb {P} (X\in A)\approx 0}</annotation>

</semantics>

</math><img src="./af158da55ea6a6469b2a9444590b83f6c2702a2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.054ex; height:2.843ex;" alt="{\textstyle \mathbb {P} (X\in A)\approx 0}" loading="lazy">. The expected number of iterations would be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\mathbb {P} (X\in A)}}}">

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\mathbb {P} (X\in A)}}}</annotation>

</semantics>

</math><img src="./2fb108c046c8010ff8fd9aad9b7a008110af9d49.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:10.629ex; height:6.009ex;" alt="{\displaystyle {\frac {1}{\mathbb {P} (X\in A)}}}" loading="lazy">, which could be close to infinity. Moreover, even when you apply the Rejection sampling method, it is always hard to optimize the bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> for the likelihood ratio. More often than not, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is large and the rejection rate is high, the algorithm can be very inefficient. The <a href="Natural_exponential_families" class="mw-redirect" title="Natural exponential families">Natural Exponential Family</a> (if it exists), also known as exponential tilting, provides a class of proposal distributions that can lower the computation complexity, the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> and speed up the computations (see examples: working with Natural Exponential Families).

<div class="mw-heading mw-heading2"><h2 id="Rejection_sampling_using_exponential_tilting">Rejection sampling using exponential tilting</h2></div>

Given a random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\sim F(\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\sim F(\cdot )}</annotation>

</semantics>

</math><img src="./f4a61b6e848fdce0ec791a1adc4ab485be7749a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.275ex; height:2.843ex;" alt="{\displaystyle X\sim F(\cdot )}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(x)=\mathbb {P} (X\leq x)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(x)=\mathbb {P} (X\leq x)}</annotation>

</semantics>

</math><img src="./1a4cb2e85047195d518ef6587c570c1ee9a9a3c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.616ex; height:2.843ex;" alt="{\displaystyle F(x)=\mathbb {P} (X\leq x)}" loading="lazy"> is the target distribution. Assume for simplicity, the density function can be explicitly written as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy">. Choose the proposal as

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}F_{\theta }(x)&=\mathbb {E} \left[\exp(\theta X-\psi (\theta ))\mathbb {I} (X\leq x)\right]\\&=\int _{-\infty }^{x}e^{\theta y-\psi (\theta )}f(y)dy\\g_{\theta }(x)&=F'_{\theta }(x)=e^{\theta x-\psi (\theta )}f(x)\end{aligned}}}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)}">

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)}</annotation>

</semantics>

</math><img src="./f2ef12baca1a084094bf781fe41ebf974297b78a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.662ex; height:2.843ex;" alt="{\displaystyle \psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta =\{\theta :\psi (\theta )<\infty \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta =\{\theta :\psi (\theta )<\infty \}}</annotation>

</semantics>

</math><img src="./c48b925fecba389a7a43e6ba8dfe0a657583ae36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.094ex; height:2.843ex;" alt="{\displaystyle \Theta =\{\theta :\psi (\theta )<\infty \}}" loading="lazy">. Clearly, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{F_{\theta }(\cdot )\}_{\theta \in \Theta }}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{F_{\theta }(\cdot )\}_{\theta \in \Theta }}</annotation>

</semantics>

</math><img src="./f8aaf5bc25502c9559f89a4f11482a45f89358ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.657ex; height:2.843ex;" alt="{\displaystyle \{F_{\theta }(\cdot )\}_{\theta \in \Theta }}" loading="lazy">, is from a <a href="Natural_exponential_family" title="Natural exponential family">natural exponential family</a>. Moreover, the likelihood ratio is

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z(x)={\frac {f(x)}{g_{\theta }(x)}}={\frac {f(x)}{e^{\theta x-\psi (\theta )}f(x)}}=e^{-\theta x+\psi (\theta )}}</annotation>

</semantics>

</math>

Note that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \psi (\theta )<\infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \psi (\theta )<\infty }</annotation>

</semantics>

</math><img src="./c03a2aaf0aefb5454f889984ed02f6aa3f57b883.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.835ex; height:2.843ex;" alt="{\displaystyle \psi (\theta )<\infty }" loading="lazy"> implies that it is indeed a <a href="Cumulant-generating_function" class="mw-redirect" title="Cumulant-generating function">cumulant-generation function</a>, that is,

</mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }}</annotation>

</semantics>

</math><img src="./739d6e77f28327304cbf093f4577c70b498d298b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:40.639ex; height:3.009ex;" alt="{\displaystyle \psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }}" loading="lazy">.</dd></dl>

It is easy to derive the cumulant-generation function of the proposal and therefore the proposal's cumulants.

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\psi _{\theta }(\eta )&=\log \left(\mathbb {E} _{\theta }\exp(\eta X)\right)=\psi (\theta +\eta )-\psi (\theta )<\infty \\\mathbb {E} _{\theta }(X)&=\left.{\frac {\partial \psi _{\theta }(\eta )}{\partial \eta }}\right|_{\eta =0}\\\mathrm {Var} _{\theta }(X)&=\left.{\frac {\partial ^{2}\psi _{\theta }(\eta )}{\partial ^{2}\eta }}\right|_{\eta =0}\end{aligned}}}</annotation>

</semantics>

</math><img src="./a1378ee925e3d7285576489f1e4cae0512b073ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.171ex; width:52.889ex; height:17.509ex;" alt="{\displaystyle {\begin{aligned}\psi _{\theta }(\eta )&=\log \left(\mathbb {E} _{\theta }\exp(\eta X)\right)=\psi (\theta +\eta )-\psi (\theta )<\infty \\\mathbb {E} _{\theta }(X)&=\left.{\frac {\partial \psi _{\theta }(\eta )}{\partial \eta }}\right|_{\eta =0}\\\mathrm {Var} _{\theta }(X)&=\left.{\frac {\partial ^{2}\psi _{\theta }(\eta )}{\partial ^{2}\eta }}\right|_{\eta =0}\end{aligned}}}" loading="lazy"></dd></dl></dd></dl>

As a simple example, suppose under <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(\cdot )}</annotation>

</semantics>

</math><img src="./ae8ad845eb97afa8e3c01816edf98f82a2b665ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.197ex; height:2.843ex;" alt="{\displaystyle F(\cdot )}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\sim \mathrm {N} (\mu ,\sigma ^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\sim \mathrm {N} (\mu ,\sigma ^{2})}</annotation>

</semantics>

</math><img src="./61a0d33916a55d5d00a0d61c5fe64991654e0b7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.451ex; height:3.176ex;" alt="{\displaystyle X\sim \mathrm {N} (\mu ,\sigma ^{2})}" loading="lazy">, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \psi (\theta )=\mu \theta +{\frac {\sigma ^{2}\theta ^{2}}{2}}}">

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \psi (\theta )=\mu \theta +{\frac {\sigma ^{2}\theta ^{2}}{2}}}</annotation>

</semantics>

</math><img src="./e1759976c7625574fa42d62856a10438d26d782f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:17.055ex; height:4.009ex;" alt="{\textstyle \psi (\theta )=\mu \theta +{\frac {\sigma ^{2}\theta ^{2}}{2}}}" loading="lazy">. The goal is to sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X|X\in \left[b,\infty \right]}">

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X|X\in \left[b,\infty \right]}</annotation>

</semantics>

</math><img src="./636c3f2bbc375c8db222d2822d2477cfc3029fde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.096ex; height:2.843ex;" alt="{\displaystyle X|X\in \left[b,\infty \right]}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b>\mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b>\mu }</annotation>

</semantics>

</math><img src="./c02d36f317d4fe3b47ae5bcb26ca7f10c31dafdf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.498ex; height:2.676ex;" alt="{\displaystyle b>\mu }" loading="lazy">. The analysis goes as follows:

<ul><li>Choose the form of the proposal distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{\theta }(\cdot )}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{\theta }(\cdot )}</annotation>

</semantics>

</math><img src="./eb46f6062e27f72d44d4c254b5cd332bd3261064.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.954ex; height:2.843ex;" alt="{\displaystyle F_{\theta }(\cdot )}" loading="lazy">, with cumulant-generating function as</li></ul>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\theta )=(\mu +\theta \sigma ^{2})\eta +{\frac {\sigma ^{2}\eta ^{2}}{2}}}</annotation>

</semantics>

</math><img src="./c7e009075f95a60dacfa02483b1ccd3d4daf3a41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:45.175ex; height:4.343ex;" alt="{\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\theta )=(\mu +\theta \sigma ^{2})\eta +{\frac {\sigma ^{2}\eta ^{2}}{2}}}" loading="lazy">,</dd></dl></dd></dl>

<dl><dd>which further implies it is a normal distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})}">

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})}</annotation>

</semantics>

</math><img src="./867ef5a65b05a52800e3141dd83425ab64c3607f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.688ex; height:3.176ex;" alt="{\displaystyle \mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})}" loading="lazy">.</dd></dl>

<ul><li>Decide the well chosen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta ^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta ^{*}}</annotation>

</semantics>

</math><img src="./5c77b69ba747144843a16bb2e053e9fcd8583735.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.343ex;" alt="{\displaystyle \theta ^{*}}" loading="lazy"> for the proposal distribution. In this setup, the intuitive way to choose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta ^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta ^{*}}</annotation>

</semantics>

</math><img src="./5c77b69ba747144843a16bb2e053e9fcd8583735.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.343ex;" alt="{\displaystyle \theta ^{*}}" loading="lazy"> is to set</li></ul>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b}</annotation>

</semantics>

</math><img src="./5eff024bbf3925c45e0a23c73aac6294e2895e5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.255ex; height:3.176ex;" alt="{\displaystyle \mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b}" loading="lazy">,</dd></dl></dd>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}.}</annotation>

</semantics>

</math><img src="./a273f2b48ecdb369cbb3fe5b3e4a38449aef531d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:11.966ex; height:5.676ex;" alt="{\displaystyle \theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}.}" loading="lazy"> The proposal distribution is thus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{\theta ^{*}}(x)=\mathrm {N} (b,\sigma ^{2})}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{\theta ^{*}}(x)=\mathrm {N} (b,\sigma ^{2})}</annotation>

</semantics>

</math><img src="./be0b2d5b56c6a155157d6a539f947aa56d66ec09.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.15ex; height:3.176ex;" alt="{\displaystyle g_{\theta ^{*}}(x)=\mathrm {N} (b,\sigma ^{2})}" loading="lazy">.</dd></dl>

<ul><li>Explicitly write out the target, the proposal and the likelihood ratio</li></ul>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}f_{X|X\geq b}(x)&={\frac {f(x)\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\\g_{\theta ^{*}}(x)&=f(x)\exp(\theta ^{*}x-\psi (\theta ^{*}))\\Z(x)&={\frac {f_{X|X\geq b}(x)}{g_{\theta ^{*}}(x)}}={\frac {\exp(-\theta ^{*}x+\psi (\theta ^{*}))\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\end{aligned}}}</annotation>

</semantics>

</math></dd></dl>

<ul><li>Derive the bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> for the likelihood ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z(x)}</annotation>

</semantics>

</math><img src="./6c2ffb6f5d6e9eeab2867ef3c37ea13f9c294ac8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.819ex; height:2.843ex;" alt="{\displaystyle Z(x)}" loading="lazy">, which is a decreasing function for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in [b,\infty ]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in [b,\infty ]}</annotation>

</semantics>

</math><img src="./49f20788c9a89c22df431d305ef569115f50cb0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.819ex; height:2.843ex;" alt="{\displaystyle x\in [b,\infty ]}" loading="lazy">, therefore</li></ul>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

</mrow>

<mrow>

<mrow>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=Z(b)={\frac {\exp(-\theta ^{*}b+\psi (\theta ^{*}))}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} \left(\mathrm {N} (0,1)\geq {\frac {b-\mu }{\sigma }}\right)}}}</annotation>

</semantics>

</math></dd></dl>

<ul><li>Rejection sampling criterion: for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\sim \mathrm {Unif} (0,1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U\sim \mathrm {Unif} (0,1)}</annotation>

</semantics>

</math><img src="./3c86fdfc26e7e426f8de4b9f74353f631a59ce7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.597ex; height:2.843ex;" alt="{\displaystyle U\sim \mathrm {Unif} (0,1)}" loading="lazy">, if</li></ul>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U\leq {\frac {Z(x)}{M}}=e^{-\theta ^{*}(x-b)}\mathbb {I} (x\geq b)}</annotation>

</semantics>

</math></dd></dl>

holds, accept the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">; if not, continue sampling new <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}">

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}</annotation>

</semantics>

</math><img src="./838b4992d2174ed336314c5f50f89cae26ed0924.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.42ex; height:3.009ex;" alt="{\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}" loading="lazy"> and new <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle U\sim \mathrm {Unif} (0,1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle U\sim \mathrm {Unif} (0,1)}</annotation>

</semantics>

</math><img src="./90b60f20e272d11f2e723b6b5a69c2372f686ab0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.597ex; height:2.843ex;" alt="{\textstyle U\sim \mathrm {Unif} (0,1)}" loading="lazy"> until acceptance.

For the above example, as the measurement of the efficiency, the expected number of the iterations the natural exponential family based rejection sampling method is of order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">, that is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M(b)=O(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M(b)=O(b)}</annotation>

</semantics>

</math><img src="./c254ac494f1237c983ee95ad7d2acb77e4401b9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.928ex; height:2.843ex;" alt="{\displaystyle M(b)=O(b)}" loading="lazy">, while under the naive method, the expected number of the iterations is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}">

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<msup>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}</annotation>

</semantics>

</math><img src="./da1ccd93f580bdae5993b5df3d9909951c33d10d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:22.268ex; height:6.176ex;" alt="{\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}" loading="lazy">, which is far more inefficient.

In general, <a href="Exponential_tilting" title="Exponential tilting">exponential tilting</a> a parametric class of proposal distribution, solves the optimization problems conveniently, with its useful properties that directly characterize the distribution of the proposal. For this type of problem, to simulate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> conditionally on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\in A}</annotation>

</semantics>

</math><img src="./836f2ffc52e48e3b9053b53e5e238c0c03a03ff1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.564ex; height:2.176ex;" alt="{\displaystyle X\in A}" loading="lazy">, among the class of simple distributions, the trick is to use natural exponential family, which helps to gain some control over the complexity and considerably speed up the computation. Indeed, there are deep mathematical reasons for using natural exponential family.

<div class="mw-heading mw-heading2"><h2 id="Drawbacks">Drawbacks</h2></div>

Rejection sampling requires knowing the target distribution (specifically, ability to evaluate target PDF at any point).

Rejection sampling can lead to a lot of unwanted samples being taken if the function being sampled is highly concentrated in a certain region, for example a function that has a spike at some location. For many distributions, this problem can be solved using an adaptive extension (see <a href="#Adaptive_rejection_sampling">adaptive rejection sampling</a>), or with an appropriate change of variables with the method of the <a href="Ratio_of_uniforms" title="Ratio of uniforms">ratio of uniforms</a>. In addition, as the dimensions of the problem get larger, the ratio of the embedded volume to the "corners" of the embedding volume tends towards zero, thus a lot of rejections can take place before a useful sample is generated, thus making the algorithm inefficient and impractical. See <a href="Curse_of_dimensionality" title="Curse of dimensionality">curse of dimensionality</a>. In high dimensions, it is necessary to use a different approach, typically a Markov chain Monte Carlo method such as <a href="Metropolis_sampling" class="mw-redirect" title="Metropolis sampling">Metropolis sampling</a> or <a href="Gibbs_sampling" title="Gibbs sampling">Gibbs sampling</a>. (However, Gibbs sampling, which breaks down a multi-dimensional sampling problem into a series of low-dimensional samples, may use rejection sampling as one of its steps.)

<div class="mw-heading mw-heading2"><h2 id="Adaptive_rejection_sampling">Adaptive rejection sampling</h2></div>

For many distributions, finding a proposal distribution that includes the given distribution without a lot of wasted space is difficult. An extension of rejection sampling that can be used to overcome this difficulty and efficiently sample from a wide variety of distributions (provided that they have <a href="Logarithmically_concave_function" title="Logarithmically concave function">log-concave</a> density functions, which is in fact the case for most of the common distributions—even those whose density functions are not concave themselves) is known as adaptive rejection sampling (ARS).

There are three basic ideas to this technique as ultimately introduced by Gilks in 1992:<a href="#cite_note-7">[7]</a>

<ol><li>If it helps, define your envelope distribution in log space (e.g. log-probability or log-density) instead. That is, work with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\left(x\right)=\log g\left(x\right)}">

<mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\left(x\right)=\log g\left(x\right)}</annotation>

</semantics>

</math><img src="./f69330c231fef9275c012d928d1d80f305e21367.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.964ex; height:2.843ex;" alt="{\displaystyle h\left(x\right)=\log g\left(x\right)}" loading="lazy"> instead of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g\left(x\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g\left(x\right)}</annotation>

</semantics>

</math><img src="./af03f370b3192f6ecb20ca164435bb064477951c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.642ex; height:2.843ex;" alt="{\displaystyle g\left(x\right)}" loading="lazy"> directly.

<ul><li>Often, distributions that have algebraically messy density functions have reasonably simpler log density functions (i.e. when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\left(x\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\left(x\right)}</annotation>

</semantics>

</math><img src="./653b89efce2f12f2c8bb8a5536ac569fe73e8271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.805ex; height:2.843ex;" alt="{\displaystyle f\left(x\right)}" loading="lazy"> is messy, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log f\left(x\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log f\left(x\right)}</annotation>

</semantics>

</math><img src="./12324f52991b4f10748c474c231931c4e09500d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.164ex; height:2.843ex;" alt="{\displaystyle \log f\left(x\right)}" loading="lazy"> may be easier to work with or, at least, closer to piecewise linear).</li></ul></li>

<li>Instead of a single uniform envelope density function, use a piecewise <a href="Linear_density" title="Linear density">linear density</a> function as your envelope instead.

<ul><li>Each time you have to reject a sample, you can use the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\left(x\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\left(x\right)}</annotation>

</semantics>

</math><img src="./653b89efce2f12f2c8bb8a5536ac569fe73e8271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.805ex; height:2.843ex;" alt="{\displaystyle f\left(x\right)}" loading="lazy"> that you evaluated, to improve the piecewise approximation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\left(x\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\left(x\right)}</annotation>

</semantics>

</math><img src="./a699dd39a3ad1079e9dcb7a71ddc8e9ffb011bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.865ex; height:2.843ex;" alt="{\displaystyle h\left(x\right)}" loading="lazy">. This therefore reduces the chance that your next attempt will be rejected. Asymptotically, the probability of needing to reject your sample should converge to zero, and in practice, often very rapidly.</li>

<li>As proposed, any time we choose a point that is rejected, we tighten the envelope with another line segment that is tangent to the curve at the point with the same x-coordinate as the chosen point.</li>

<li>A piecewise linear model of the proposal log distribution results in a set of piecewise <a href="Exponential_distribution" title="Exponential distribution">exponential distributions</a> (i.e. segments of one or more exponential distributions, attached end to end). Exponential distributions are well behaved and well understood. The logarithm of an exponential distribution is a straight line, and hence this method essentially involves enclosing the logarithm of the density in a series of line segments. This is the source of the log-concave restriction: if a distribution is log-concave, then its logarithm is concave (shaped like an upside-down U), meaning that a line segment tangent to the curve will always pass over the curve.</li>

<li>If not working in log space, a piecewise linear density function can also be sampled via triangle distributions<a href="#cite_note-8">[8]</a></li></ul></li>

<li>We can take even further advantage of the (log) concavity requirement, to potentially avoid the cost of evaluating <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\left(x\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\left(x\right)}</annotation>

</semantics>

</math><img src="./653b89efce2f12f2c8bb8a5536ac569fe73e8271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.805ex; height:2.843ex;" alt="{\displaystyle f\left(x\right)}" loading="lazy"> when your sample is accepted.

<ul><li>Just like we can construct a piecewise linear upper bound (the "envelope" function) using the values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\left(x\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\left(x\right)}</annotation>

</semantics>

</math><img src="./a699dd39a3ad1079e9dcb7a71ddc8e9ffb011bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.865ex; height:2.843ex;" alt="{\displaystyle h\left(x\right)}" loading="lazy"> that we had to evaluate in the current chain of rejections, we can also construct a piecewise linear lower bound (the "squeezing" function) using these values as well.</li>

<li>Before evaluating (the potentially expensive) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\left(x\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\left(x\right)}</annotation>

</semantics>

</math><img src="./653b89efce2f12f2c8bb8a5536ac569fe73e8271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.805ex; height:2.843ex;" alt="{\displaystyle f\left(x\right)}" loading="lazy"> to see if your sample will be accepted, we may already know if it will be accepted by comparing against the (ideally cheaper) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{l}\left(x\right)}">

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{l}\left(x\right)}</annotation>

</semantics>

</math><img src="./00b676b5652e17f7806de072fbbcaa37c3853a35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.358ex; height:2.843ex;" alt="{\displaystyle g_{l}\left(x\right)}" loading="lazy"> (or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{l}\left(x\right)}">

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{l}\left(x\right)}</annotation>

</semantics>

</math><img src="./09b77cff174404dd376b0e7097597e7f8bd9fbc7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.588ex; height:2.843ex;" alt="{\displaystyle h_{l}\left(x\right)}" loading="lazy"> in this case) squeezing function that have available.</li>

<li>This squeezing step is optional, even when suggested by Gilks. At best it saves you from only one extra evaluation of your (messy and/or expensive) target density. However, presumably for particularly expensive density functions (and assuming the rapid convergence of the rejection rate toward zero) this can make a sizable difference in ultimate runtime.</li></ul></li></ol>

The method essentially involves successively determining an envelope of straight-line segments that approximates the logarithm better and better while still remaining above the curve, starting with a fixed number of segments (possibly just a single tangent line). Sampling from a truncated exponential random variable is straightforward. Just take the log of a uniform random variable (with appropriate interval and corresponding truncation).

Unfortunately, ARS can only be applied for sampling from log-concave target densities. For this reason, several extensions of ARS have been proposed in literature for tackling non-log-concave target distributions.<a href="#cite_note-9">[9]</a><a href="#cite_note-10">[10]</a><a href="#cite_note-11">[11]</a> Furthermore, different combinations of ARS and the Metropolis-Hastings method have been designed in order to obtain a universal sampler that builds a self-tuning proposal densities (i.e., a proposal automatically constructed and adapted to the target). This class of methods are often called as Adaptive Rejection Metropolis Sampling (ARMS) algorithms.<a href="#cite_note-12">[12]</a><a href="#cite_note-13">[13]</a> The resulting adaptive techniques can be always applied but the generated samples are correlated in this case (although the correlation vanishes quickly to zero as the number of iterations grows).

<ul><li><a href="Inverse_transform_sampling" title="Inverse transform sampling">Inverse transform sampling</a></li>

<li><a href="Ratio_of_uniforms" title="Ratio of uniforms">Ratio of uniforms</a></li>

<li><a href="Pseudo-random_number_sampling" class="mw-redirect" title="Pseudo-random number sampling">Pseudo-random number sampling</a></li>

<li><a href="Ziggurat_algorithm" title="Ziggurat algorithm">Ziggurat algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCasellaRobertWells2004" class="citation book cs1">Casella, George; Robert, Christian P.; Wells, Martin T. (2004). Generalized Accept-Reject sampling schemes. Institute of Mathematical Statistics. pp. 342–347. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Flnms%2F1196285403">10.1214/lnms/1196285403</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780940600614</bdi>.</cite>

</li>

<li id="cite_note-radford03-2"><a href="#cite_ref-radford03_2-0">^</a> <cite id="CITEREFNeal2003" class="citation journal cs1">Neal, Radford M. (2003). <a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faos%2F1056562461">"Slice Sampling"</a>. <a href="Annals_of_Statistics" title="Annals of Statistics">Annals of Statistics</a>. 31 (3): 705–767. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faos%2F1056562461">10.1214/aos/1056562461</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1994729">1994729</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1051.65007">1051.65007</a>.</cite>

</li>

<li id="cite_note-bishop06-3"><a href="#cite_ref-bishop06_3-0">^</a> <cite id="CITEREFBishop2006" class="citation book cs1">Bishop, Christopher (2006). "11.4: Slice sampling". Pattern Recognition and Machine Learning. <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-31073-2</bdi>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFForsythe1972" class="citation journal cs1">Forsythe, George E. (1972). <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2005864">"Von Neumann's Comparison Method for Random Sampling from the Normal and Other Distributions"</a>. Mathematics of Computation. 26 (120): 817–826. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2005864">10.2307/2005864</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0025-5718">0025-5718</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2005864">2005864</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFLegaultMelbourne2019" class="citation journal cs1">Legault, Geoffrey; Melbourne, Brett A. (2019-03-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/s12080-018-0386-z">"Accounting for environmental change in continuous-time stochastic population models"</a>. Theoretical Ecology. 12 (1): 31–48. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs12080-018-0386-z">10.1007/s12080-018-0386-z</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1874-1746">1874-1746</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFThomopoulos2012" class="citation book cs1">Thomopoulos, Nick T. (2012-12-19). Essentials of Monte Carlo Simulation: Statistical Methods for Building Simulation Models (2013th ed.). New York, NY Heidelberg: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4614-6021-3</bdi>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFGilksWild1992" class="citation journal cs1">Gilks, W. R.; Wild, P. (1992). "Adaptive Rejection Sampling for Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 41 (2): 337–348. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2347565">10.2307/2347565</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2347565">2347565</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFThomasLuk2007" class="citation journal cs1">Thomas, D. B.; Luk, W. (2007). "Non-uniform random number generation through piecewise linear approximations". IET Computers & Digital Techniques. 1 (4): 312–321. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1049%2Fiet-cdt%3A20060188">10.1049/iet-cdt:20060188</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFHörmann1995" class="citation journal cs1">Hörmann, Wolfgang (1995-06-01). "A Rejection Technique for Sampling from T-concave Distributions". ACM Trans. Math. Softw. 21 (2): 182–193. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.6055">10.1.1.56.6055</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F203082.203089">10.1145/203082.203089</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0098-3500">0098-3500</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFEvansSwartz1998" class="citation journal cs1">Evans, M.; Swartz, T. (1998-12-01). "Random Variable Generation Using Concavity Properties of Transformed Densities". Journal of Computational and Graphical Statistics. 7 (4): 514–528. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.9001">10.1.1.53.9001</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1390680">10.2307/1390680</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1390680">1390680</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFGörürTeh2011" class="citation journal cs1">Görür, Dilan; Teh, Yee Whye (2011-01-01). "Concave-Convex Adaptive Rejection Sampling". Journal of Computational and Graphical Statistics. 20 (3): 670–691. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1198%2Fjcgs.2011.09058">10.1198/jcgs.2011.09058</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1061-8600">1061-8600</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFGilksBestTan1995" class="citation journal cs1">Gilks, W. R.; <a href="Nicky_Best" title="Nicky Best">Best, N. G.</a>; Tan, K. K. C. (1995-01-01). "Adaptive Rejection Metropolis Sampling within Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2986138">10.2307/2986138</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2986138">2986138</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFMeyerCaiPerron2008" class="citation journal cs1">Meyer, Renate; Cai, Bo; Perron, François (2008-03-15). "Adaptive rejection Metropolis sampling using Lagrange interpolation polynomials of degree 2". Computational Statistics & Data Analysis. 52 (7): 3408–3423. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.csda.2008.01.005">10.1016/j.csda.2008.01.005</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFRobertCasella2004" class="citation book cs1">Robert, C. P.; Casella, G. (2004). Monte Carlo Statistical Methods (Second ed.). New York: Springer-Verlag.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-03" href="https://en.wikipedia.org/wiki/?title=Rejection_sampling&oldid=1303987796">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>